Finite Automata
Q1.
Consider the following language: L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \} Which one of the following deterministic finite automata accepts L?Q2.
Minimum number of states required in DFA accepting binary strings not ending in "101" isQ3.
Consider the following deterministic finite automaton (DFA)The number of strings of length 8 accepted by the above automaton is _________Q4.
Given a language L, define L^{i} as follows: L^{0}=\{\varepsilon \} L^{i}=L^{i-1} \cdot L for all i \gt 0 The order of a language L is defined as the smallest k such that L^{k}=L^{k+1}. Consider the language L1 (over alphabet 0) accepted by the following automaton. The order of L1 is ______Q5.
The minimum possible number of states of a deterministic automaton that accepts the regular language L=\{w_{1}aw_{2}|w_{1},w_{2}\in \{a,b\}^{*},|w_{1}|=2,|w_{2}|\geq 3\} is ____Q6.
Let \Sigma be the set of all bijections from {1,...,5} to {1,...,5}, where id denotes the identity function, i.e. id(j)=j,\forall j. Let \circ denote composition on functions. For a string x = x_1x_2 ... x_n \in \Sigma ^n, n \geq 0, let \pi(x) = x_1\circ x_2\circ ... \circ x_n. Consider the language L = \{x \in \Sigma ^* | \pi(x) = id\}. The minimum number of states in any DFA accepting L is _________ .Q7.
Consider the language L over the alphabet {0, 1}, given below:L = \{w \in \{0, 1\}^* | w \text{ does not contain three or more consecutive 1's} \}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is _____.Q8.
Let \delta denote that transition function and \hat{\delta} denote the extended transition function of the \epsilon- NFA whose transition table is given below: Then \hat{\delta}(q_{2},aba) is ____Q10.
Consider the following language. L={x \in \{a,b\}^*| number of a's in x divisible by 2 but not divisible by 3} The minimum number of states in DFA that accepts L is _______